#include <vector>
#include <queue>

using namespace std;

// 喧闹和富有
// 从 0 到 n - 1 编号，其中每个人都有不同数目的钱，以及不同程度的安静值
// 给你一个数组richer，其中richer[i] = [ai, bi] 表示 
// person ai 比 person bi 更有钱
// 还有一个整数数组 quiet ，其中 quiet[i] 是 person i 的安静值
// richer 中所给出的数据 逻辑自洽
// 也就是说，在 person x 比 person y 更有钱的同时，不会出现
// person y 比 person x 更有钱的情况
// 现在，返回一个整数数组 answer 作为答案，其中 answer[x] = y 的前提是,
// 在所有拥有的钱肯定不少于 person x 的人中，
// person y 是最安静的人（也就是安静值 quiet[y] 最小的人）。
// 测试链接 : https://leetcode.cn/problems/loud-and-rich/

class Solution 
{
public:
    vector<int> loudAndRich(vector<vector<int>>& richer, vector<int>& quiet) 
    {
        int n = quiet.size();
        vector<vector<int>> g(n);
        vector<int> indegree(n);
        // 建图
        for(auto& r : richer)
        {
            int x = r[0], y = r[1];
            g[x].push_back(y);
            ++indegree[y];
        }

        queue<int> q;
        vector<int> ret(n);
        // ret[i] 是比 i 有钱的人中最安静的那个，可以是自己
        for(int i = 0; i < n; ++i)
        {
            ret[i] = i;
            // 入度为 0 的节点入队列
            if(!indegree[i]) q.push(i);
        }

        while(!q.empty())
        {
            int x = q.front();
            q.pop();
            for(int y : g[x])
            {
                // x 是比 y 有钱的人
                // quiet[ret[x]] 是比 x 有钱的人中最安静那个人的安静值
                if(quiet[ret[x]] < quiet[ret[y]]) ret[y] = ret[x];
                if(--indegree[y] == 0) q.push(y);
            }
        }
        return ret;
    }
};